package recursive;

import common.TreeNode;

/**
 * 验证二叉搜索树
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 * 给定一棵树，左边节点都比右边节点小，说明这棵树是有效的
 * 解题思路：整棵树的根节点左边所有节点都要比根节点小，右边所有节点都要比根节点大，且每一个子树都要满足该条件。
 *         只考虑当前节点的子节点和父节点大小比较，是没办法满足条件的
 *         从根节点往左遍历，可选数值区间是小于根节点的，往右遍历，可选数值区间是大于根节点的，
 *         由此，只要限制好左右区间，就能保证左边子树的所有节点都是小于根节点，右边子树所有节点都是大于根节点
 * 注意：1、确定递归边界——当前节点为空的时候，或者已经发现不是有效二叉搜索树了
 *      2、区间确定有加减操作，注意是否超出数值类型最大边界
 *      3、必须保证每个根节点的整体左子树都小于根节点，整体右子树都大于根节点
 * 测试案例：1、[2]——true
 *         2、[2,1]——true
 *         3、[1,1]——false
 *         4、[2,1,1]——false
 *         5、[2,null,1]——false
 *         6、[2,1,3]——true
 *         7、[5,1,4,null,null,3,6]——false
 *         8、[5,4,6,null,null,3,7]——false
 *         9、[5,2,8,1,6,4,9]——false
 *         10、[32,26,47,19,null,null,56,null,27]——false
 *         [2][2,1][1,1][2,1,1][2,null,1][2,1,3][5,1,4,null,null,3,6][32,26,47,19,null,null,56,null,27][5,4,6,null,null,3,7][5,2,8,1,6,4,9]
 */
public class ValidateBinarySearchTree {
    private boolean result = true;
    public boolean isValidBST(TreeNode root) {
        // 为了防止判断大小的时候超出 int 界限，采用 long 类型
        perform(root, -2147483648L, 2147483647L);
        return result;
    }

    private void perform(TreeNode node, long leftInterval, long rightInterval){
        if (!result || node == null)
            return;
        if (!(node.val >= leftInterval && node.val <= rightInterval)){
            result = false;
            return;
        }

        perform(node.left, leftInterval,  node.val-1L);
        perform(node.right, node.val+1L, rightInterval);
    }
}
